Python数据结构之栈和队列的实现(详细无敌版！！！！) |
您所在的位置：网站首页 › python 堆栈深度 › Python数据结构之栈和队列的实现(详细无敌版！！！！) |
Python数据结构之栈和队列的实现(详细无敌版！！！！)
|
Python数据结构
容器数据结构的理解栈和栈的实现定义实现栈的简单应用
队列和队列的实现定义队列的实现双端队列及其实现阻塞队列
容器数据结构的理解
在常用的数据结构中，有一批结构被称为容器，一个容器结构里总包含一组其它类型的数据对象，称为其元素，支持对这些元素的存储、管理和使用。一类容器具有相同性质，支持同一组操作，可以被定义为一个抽象的数据类型 最常用的数据容器即为：栈(stack)和队列(queue) 栈和栈的实现 定义 •先进后出，后进先出，并且只能在栈顶进出 •栈是一种“操作受限”的线性表，只允许在一端插入和删除数据元素，在满足先进后出、后进先出的特性时，应该使用栈 如图所示： 用顺序表实现的栈成为顺序栈，用链表实现的栈叫做链式栈。 顺序栈的实现相对简单，因为对于栈的操作可以通过对顺序表的操作方法实现，不用自己定义，直接调用即可，相对简单 栈相当于一个类，实现栈的过程为方法，具体操作有判空操作、添加元素操作、弹出栈顶元素操作、返回栈顶元素操作、求栈长度操作、遍历操作等等，实现如下： class Stack(object): """栈，使用顺序表实现""" def __init__(self): """定义空栈""" self.__items = [] def is_empty(self): """判断栈是否为空""" return self.__items == [] def push(self, item): """添加一个新元素item到栈顶""" self.__items.append(item) def pop(self): """弹出栈顶元素，有返回值""" return self.__items.pop() def peek(self): """返回栈顶元素，有返回值""" # 判断栈是否为空 if self.is_empty(): return None else: return self.__items[-1] def size(self): """返回栈中的元素个数""" return len(self.__items) def travel(self): """遍历栈中的元素""" for item in self.__items: print(item) if __name__ == '__main__': s = Stack() s.push(7) s.push(8) s.push(9) s.pop() print(s.size()) print(s.is_empty()) print(s.peek()) s.travel()测试结果如下： 2 False 8 7 8 栈的简单应用浏览器的前进后退： 当你依次访问完一串页面a-b-c之后，点击浏览器的后退按钮，就可以查看之前浏览过的页面b和a。当你后退到页面a，点击前进按钮，就可以重新查看页面b和c。但是，如果你后退到页面b后，点击了新的页面d，那就无法再通过前进、后退功能查看页面c了 1.定义 特点：先进者先出。 操作： 入队enqueue：放一个数据到队列尾部 出队dequeue：从队列头部取一个元素 队列也是一种操作受限制的线性表数据结构 包括一些额外特性的队列，比如循环队列、阻塞队列、并发队列等，在很多偏底层系统、框架、中间件的开发中起着关键作用 队列的实现队列的实现也是使用顺序表list来实现，相关操作与list的操作相关，队列相当于一个类，实现队列的过程为方法，具体操作有判空操作、添加元素操作、弹出元素操作、求队列长度操作、遍历操作等等，实现如下： class Queue(object): def __init__(self): """初始化，即定义一个空队列""" self.__items = [] def is_empty(self): """判空操作，判断队列是否为空""" return self.__items == [] def enqueue(self, item): """向队列中添加新元素""" self.__items.append(item) def dequeue(self): """返回队列中的第一个元素""" return self.__items.pop(0) def size(self): """返回队列中的元素个数""" return len(self.__items) def travel(self): """遍历队列中的元素""" for item in self.__items: print(item) if __name__ == '__main__': q = Queue() print(q.is_empty()) q.enqueue(7) q.enqueue(8) q.enqueue(9) print(q.is_empty()) print(q.size()) print(q.dequeue()) q.dequeue() q.travel()实现结果如下： True False 3 7 9 双端队列及其实现全名double-ended-queue，一种具有队列和栈的性质的特殊的数据结构 结构如图所示： 元素可以从两端弹出，其限定插入和删除操作在队列的两端进行，可以在队列任意一端入队和出队 实现如下： class Dequeue(object): """初始化队列""" def __init__(self): self.__items = [] def is_empty(self): """判断队列是否为空""" return self.__items == [] def size(self): """返回队列中元素个数""" return len(self.__items) def add_front(self, item): """从队头添加一个新元素item""" self.__items.insert(0, item) def add_rear(self, item): """从队尾添加一个新元素item""" self.__items.append(item) def remove_front(self): """从队头删除一个元素""" return self.__items.pop(0) def remove_rear(self): """从队尾删除一个元素""" return self.__items.pop() def travel(self): """从队头遍历队列""" for item in self.__items: print(item) if __name__ == '__main__': d = Dequeue() print(d.is_empty()) d.add_front(7) d.add_front(8) d.add_rear(9) d.travel() d.remove_front() d.travel() print(d.size())实现结果如下： True 8 7 9 7 9 2 阻塞队列input()函数调用时等待输入，即为阻塞 阻塞队列在队列基础上增加了阻塞操作： •在队列为空的的时候，从队头取数据会被阻塞，因为此时还没有数据可取，直到队列中有了数据才能返回 •如果队列已经满了，那么插入数据的操作就会被阻塞，直到队列中有空闲位置后再插入数据，然后再返回 应用：CPU资源分配 •CPU资源是有限的，任务的处理速度与线程个数并不是线性正相关。相反，过多的线程反而会导致CPU频繁切换，处理性能下降。所以，线程池的大小一般都是综合考虑要处理任务的特点和硬件环境，来事先设置的 •如果采用链表：无限排队的无界队列 响应时间，比较敏感不合适 •如果采用顺序表：有界的队列 如果超过 直接拒绝 响应时间 敏感比较合适 |
【本文地址】